package com.fr.lintcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import org.junit.Test;

/**
*作者：furong
*日期：2017年1月22日
*时间：下午2:48:20
*/
public class Q16 {
    /**
     * @param nums: A list of integers.
     * @return: A list of unique permutations.
     */
    List<List<Integer>> rs = new ArrayList<>();

    public List<List<Integer>> permuteUnique(int[] nums) {
        List<Integer> result = new ArrayList<Integer>();
        if (nums == null || nums.length <= 0) {
            rs.add(result);
            return rs;
        }
        Arrays.sort(nums);
        int length = nums.length;
        permuteUnique(0, length - 1, nums);
        return rs;
    }

    private void permuteUnique(int i, int length, int[] nums) {
        if (i >= length) {
            save(nums);
        } else {
            for (int j = i; j <= length; j++) {
                if (check(nums, i, j)) {
                    swap(nums, i, j);
                    permuteUnique(i + 1, length, nums);
                    swap(nums, i, j);
                }
            }
        }

    }

    private boolean check(int[] nums, int i, int j) {
        for (int k = i; k < j; k++) {
            if (nums[k] == nums[j]) {
                return false;
            }
        }
        return true;
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    private void save(int[] nums) {
        List<Integer> result = new ArrayList<Integer>();
        for (int i : nums) {
            result.add(i);
        }
        rs.add(result);
    }

    @Test
    public void testA() {
        int[] nums = { 1, 2, 2, 3 };
        System.out.println(permuteUnique(nums));
    }
}
